package 并查集;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

public class GenericUnionFind<V> {
	
	private Map<V, Node<V>> nodes = new HashMap<>();
	
	public void makeSet(V value) {
		if (nodes.containsKey(value)) return;
		Node<V> node = new Node<>(value);
		nodes.put(value, node);
	}
	
	/**
	 * 找到V对应节点的根节点的Value
	 * @return
	 */
	public V find(V value) {
		Node<V> node = findNode(value);
		return node == null ? null : node.value;
	}
	
	public boolean isSame(V v1, V v2) {
		Node<V> p1 = findNode(v1);
		Node<V> p2 = findNode(v2);
		if (p1 == null || p2 == null) return false;
		return Objects.equals(p1.value, p2.value);
	}
	
	public void union(V v1, V v2) {
		Node<V> p1 = findNode(v1);
		Node<V> p2 = findNode(v2);
		if (p1 == null || p2 == null) return;
		if (Objects.equals(p1.value, p2.value)) return;
		
		if (p1.rank < p2.rank) {
			p1.parent = p2;
		} else if (p1.rank > p2.rank) {
			p2.parent = p1;
		} else {
			p1.parent = p2;
			p2.rank++;
		}
		
	}
	
	/**
	 * 找到value对应的根节点
	 * @param value
	 * @return
	 */
	private Node<V> findNode(V value) {
		Node<V> node = nodes.get(value);
		if (node == null) return null;
		while (!Objects.equals(node.value, node.parent.value)) {
			node.parent = node.parent.parent;
			node = node.parent;
		}
		return node;
	}
	
	private static class Node<V> {
		V value;
		Node<V> parent = this;
		int rank = 1;
		
		public Node(V value) {
			this.value = value;
		}
	}
}
